package cn.edu.xjtu.work.canReach;

/**
 * 1306. 跳跃游戏 III
 * 
 * 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到i+arr[i]或者i-arr[i]。
 * 
 * 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。
 * 
 * 注意，不管是什么情况下，你都无法跳到数组之外。
 */
public class Solution {
  public static void main(String[] args) {
    Solution solu = new Solution();
    int[] arr = new int[] { 3, 0, 2, 1, 2 };
    System.out.println(solu.canReach(arr, 2));
  }

  public boolean canReach(int[] arr, int start) {
    int[] mark = new int[arr.length];// 标记是否来过
    return judge(arr, start, mark);
  }

  public boolean judge(int[] arr, int start, int[] mark) {
    if (start >= arr.length || start < 0) {
      return false;
    }
    if (arr[start] == 0) {
      return true;
    }
    if (mark[start] == 1) {
      return false;
    }
    mark[start] = 1;
    return judge(arr, start - arr[start], mark) || judge(arr, start + arr[start], mark);
  }
}
